package madixin.t19;

class Solution {

    /**
     * 1次遍历,双指针
     */
    public ListNode removeNthFromEnd(ListNode head, int n) {

        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode first = dummy;
        ListNode second = dummy;

        for (int i = 1; i <= n + 1; i++) {
            second = second.next;
        }


        while (second != null) {
            first = first.next;
            second = second.next;
        }

        first.next = first.next.next;

        return dummy.next;

    }

    /**
     * 两次遍历
     */
    public ListNode removeNthFromEnd1(ListNode head, int n) {
        //在第一次遍历中，我们找出列表的长度 L
        //第二次遍历找到L-n个节点
        ListNode dummy = head;
        int l = 0;
        while (head != null) {
            l++;
            head = head.next;
        }

        head = dummy;
        if (l == n) {
            return head.next;
        }


        for (int i = 0; i < l - n - 1; i++) {
            head = head.next;
        }
        head.next = head.next.next;
        return dummy;
    }
}